#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> p;
const int N = 1e5+10;
const int MOD = 1e9+7;
int minP[N];
int phi[N];
int qpow(int x,int p){
	int res = 1;
	while(p){
		if(p & 1){
			res = 1ll*res*x%MOD;
		}
		x = 1ll*x*x%MOD;
		p >>= 1;
	}
	return res;
}
void init(int lmt){
	phi[1] = 1;
	for(int i = 2;i <= lmt;i++){
		if(!minP[i]){
			minP[i] = i;
			p.push_back(i);
			phi[i] = i - 1;
		}
		for(int j = 0;p[j] != minP[i] && 1ll*p[j]*i <= lmt;j++){
			phi[i*p[j]] = (p[j] - 1)*phi[i];
			minP[i * p[j]] = p[j];
		}
		if(1ll*minP[i] * i <= lmt){
			phi[minP[i]*i] = minP[i]*phi[i];
			minP[minP[i]*i] = minP[i];
		}
	}
}
int bp(int x){
	int res = 1;
	for(int i = 0;i < p.size() && 1ll*p[i]*p[i] <= x;i++){
		if(x % p[i] == 0){
			res = res*(p[i] - 1);
			x /= p[i];
			while(x % p[i] == 0){
				res = res*p[i];
				x /= p[i];
			}
		}
	}
	if(x != 1){
		res = res*(x - 1);
	}
	return res;
}
typedef vector<vector<int>> mat;
mat operator*(mat m1,mat m2){
	int n = m1.size();
	mat res(n,vector<int>(n));
	for(int i = 0;i < n;i++){
		for(int k = 0;k < n;k++){
			int num = m1[i][k];
			for(int j = 0;j < n;j++){
				res[i][j] = (res[i][j] + 1ll*num*m2[k][j]%MOD)%MOD;
			}
		}
	}
	return res;
}
mat val[31];
mat ksm(int p){
	if(p == 0){
		mat res(m,vector<int>(m));
		for(int i = 0;i < m;i++){
			res[i][i] = 1;
		}
		return res;
	}
	p--;
	mat res = val[0];
	for(int i = 0;i <= 30;i++){
		if((p >> i)&1){
			res = res*val[i];	
		}
	}
	return res;
}
int main(){
	int c;
	cin>>n>>m>>c;
	mat sf(m,vector<int>(m,1));
	for(int i = 1;i<=c;i++){
		int a,b;
		cin>>a>>b;
		sf[b][a] = 0;
		sf[a][b] = 0;
	}
	val[0] = sf;
	for(int i = 1;(1<<i) <= n;i++){
		val[i] = val[i - 1]*val[i - 1];
	}
	init(sqrt(n));
	int pn = bp(n);
	int ans = 0;
	for(int i = 1;i*i <= n;i++){
		if(n % i == 0){
			int tg = 0;
			mat v = ksm(i - 1);
			for(int i = 0;i<m;i++){
				for(int j = 0;j<m;j++){
					if(val[0][i][j]){
						tg = (tg + v[i][j])%MOD;
					}
				}
			}
			int p1 = (1ll*pn*phi[__gcd(i,n/i)]/phi[i]/__gcd(i,n/i));
			ans = (ans + 1ll*p1*tg%MOD)%MOD;
			if(n / i != i){
				tg = 0;
				v = ksm(n/i - 1);
				for(int i = 0;i<m;i++){
					for(int j = 0;j<m;j++){
						if(val[0][i][j]){
							tg = (tg + v[i][j])%MOD;
						}
					}
				}
				ans = (ans + 1ll*phi[i]*tg%MOD)%MOD;
			}
		}
	}
	ans = 1ll*ans*qpow(n,MOD - 2)%MOD;
	cout<<ans<<'\n';
}